package org.lql.algo.codecrush.hot100.greedy;

/**
 * @author: liangqinglong
 * @date: 2025-09-16 09:06
 * @description: 45. 跳跃游戏 II <a href="https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class Jump {

	public int jump(int[] nums) {
		int n = nums.length;
		int cur = 0;
		int ans = 0;
		while (cur < n - 1) {
			// 当前位置可到达的最远边界
			int right = cur + nums[cur];
			if (right >= n - 1) {
				return ans + 1;
			}
			int nextRight = right;
			int next = 0;
			for (int i = cur + 1; i <= right; i++) {
				if (i + nums[i] > nextRight) {
					nextRight = i + nums[i];
					next = i;
				}
			}
			cur = next;
			ans++;
		}
		return ans;
	}

	public static void main(String[] args) {
		Jump jump = new Jump();
		int[] nums = {2, 3, 1, 1, 4};
		System.out.println(jump.jump(nums));
	}
}
